package com.leetcode;

import com.leetcode.common.TreeNode;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * 236. 二叉树的最近公共祖先
 *
 * @author fy
 * @date 2022/3/30 16:08
 */
public class Solution236_1 {

    private Map<Integer, TreeNode> parent = new HashMap<>();
    private Set<Integer> visited = new HashSet<>();

    /**
     * 可以用哈希表存储所有节点的父节点，
     * 然后我们就可以利用节点的父节点信息从 p 结点开始不断往上跳，
     * 并记录已经访问过的节点，
     * 再从 q 节点开始不断往上跳，如果碰到已经访问过的节点，
     * 那么这个节点就是我们要找的最近公共祖先
     *
     * @param root
     * @param p
     * @param q
     * @return
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || p == null || q == null) {
            return null;
        }
        // 递归记录节点的父节点
        dfs(root);
        // 通过map查找p节点路径节点值并保存到set
        while (p != null) {
            visited.add(p.val);
            p = parent.get(p.val);
        }
        // 通过map查找q节点路径节点值, 如果与q的路径节点重合,
        // 则最先找到的节点是最近公共祖先节点值
        while (q != null) {
            if (visited.contains(q.val)) {
                return q;
            }
            q = parent.get(q.val);
        }
        return null;
    }

    private void dfs(TreeNode node) {
        if (node.left != null) {
            parent.put(node.left.val, node);
            dfs(node.left);
        }
        if (node.right != null) {
            parent.put(node.right.val, node);
            dfs(node.right);
        }
    }

}
